import functools


# 记忆化搜索
# class Solution(object):
#     def longestPalindromeSubseq(self, s):
#         @functools.cache
#         def dfs(i, j, last_value):
#             if j - i < 1:
#                 return 0
#             else:
#                 if s[i] == s[j]:
#                     if s[i] == last_value:
#                         return dfs(i + 1, j - 1, last_value)
#                     else:
#                         return 2 + dfs(i + 1, j - 1, s[i])
#                 else:
#                     if s[i] == last_value:
#                         return dfs(i + 1, j, last_value)
#                     else:
#                         if s[j] == last_value:
#                             return dfs(i, j - 1, last_value)
#                         else:
#                             return max(dfs(i + 1, j, last_value), dfs(i, j - 1, last_value))
#
#         return dfs(0, len(s) - 1, '')

# 动态规划
# class Solution(object):
#     def longestPalindromeSubseq(self, s):
#         n = len(s)
#         DP = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(26)]
#         for k in range(n):
#             for i in range(n - k):
#                 for z in range(26):
#                     if k == 0:
#                         DP[z][i][i + k] = 0
#                     else:
#                         if s[i] == s[i + k] and ord(s[i]) - ord('a') != z:
#                             if k == 1:
#                                 DP[z][i][i + k] = 2
#                             else:
#                                 DP[z][i][i + k] = 2 + DP[ord(s[i]) - ord('a')][i + 1][i + k - 1]
#                         else:
#                             if k == 1:
#                                 DP[z][i][i + k] = 0
#                             else:
#                                 if ord(s[i]) - ord('a') == z:
#                                     if ord(s[i + k]) - ord('a') == z:
#                                         DP[z][i][i + k] = DP[z][i + 1][i + k - 1]
#                                     else:
#                                         DP[z][i][i + k] = DP[z][i + 1][i + k]
#                                 else:
#                                     if ord(s[i + k]) - ord('a') == z:
#                                         DP[z][i][i + k] = DP[z][i][i + k - 1]
#                                     else:
#                                         DP[z][i][i + k] = max(DP[z][i][i + k - 1], DP[z][i + 1][i + k])
#         return max([DP[i][0][n - 1] for i in range(26)])

class Solution(object):
    def longestPalindromeSubseq(self, s):
        @functools.cache
        def dfs(i, j):
            if j - i < 1:
                return 0, ''
            else:
                if s[i] == s[j]:
                    next_s, next_v = dfs(i + 1, j - 1)
                    if next_v != s[i]:
                        return next_s + 2, s[i]
                next_s1, next_v1 = dfs(i + 1, j)
                next_s2, next_v2 = dfs(i, j - 1)
                if next_s1 >= next_s2:
                    return next_s1, next_v1
                else:
                    return next_s2, next_v2

        return dfs(0, len(s) - 1)[0]



data = Solution()
s = "vorvgrrbcdynnoamonjizzsabsuzioeyuvzhrrtvdynxvgtdnknocglhzrynhgrpgalmjattmqmrnmqoapylwydzmgmeemhabhcfcoszitopojmoitbmesxhhitmsnkfipwghkosjhtgmmgmgssfyvkvzpbabphffecyzhrhpalarpeujzikjyzyhmlyqmnwqfvjyrndndrpmeoptrreleghjoiwezyevvzfdyogdlsztxggpbgmvhjnal"
print(data.longestPalindromeSubseq(s))
